import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //初始化
        List<List<Integer>> res = new ArrayList<>();
        // 对数组进行排序，方便去重
        Arrays.sort(candidates);
        //调用方法
        backtrack(candidates, target, res, 0, new ArrayList<>());
        //返回集合
        return res;
    }

    public void backtrack(int[] nums, int target, List<List<Integer>> res, int start, List<Integer> list) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            // 如果当前数比剩余的目标值大，则后续的数也会大于目标值，直接跳出循环
            if (nums[i] > target) {
                break;
            }
            //去重逻辑：如果当前数字与前一个数字相同，则跳过
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            //选择当前数字
            list.add(nums[i]);
            // 递归调用，更新目标值为 target - nums[i]，并从下一个位置开始选择
            backtrack(nums, target - nums[i], res, i + 1, list);
            // 回溯：移除当前数字，尝试其他选择
            list.remove(list.size() - 1);

        }
    }

}
